﻿// 蚁群算法解决罗马尼亚问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <chrono>
#include<utility>
#include <ctime>
#include <cstdlib>
#include <random>
using namespace std;
const int info = 1;

class mapwithant
{
public:
    int distance;
    float smell;
    float possible;
    mapwithant()
    {
        smell = 1;
    }
    void workwithpointpossible()
    {
        possible = smell / distance;
    };
};
class ant
{
public:
    vector<int> P;
    int suming=0;
    int findposs(mapwithant A[20],int step[20],bool exam  = 1)
    {
        if (exam == 1) {
            float possible[20];
            float sum = 0; // 将sum移出循环外部
            for (int i = 0; i < 20; i++)
            {
                if ((A[i].distance != 1000) && (A[i].distance != 0) && step[i] == 0)
                {
                    possible[i] = A[i].possible;
                    sum += A[i].possible;
                }
                else
                {
                    possible[i] = 0;
                }
            }
            float turn = 1 / sum;
            cout << "turn" << turn << endl;
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_real_distribution<double> dis(0.0, 1.0);
            double randomNumber = dis(gen);
            float now = 0;

            for (int j = 0; j < 20; j++) // 将循环变量改为j
            {

                if ((now < randomNumber) && (randomNumber <= (now + turn * possible[j])))
                {
                    step[j] = 1;
                    return j;

                }
                else
                {
                    now = now + turn * possible[j];

                }
            }
            cout << "ant的概率选择出现问题";
            return -1;
        }
        else
        {
            pair<int, float> ans = make_pair(-1, 0);
            for (int k = 0; k < 20; k++)
            {
                if (A[k].smell > ans.second)
                {
                    ans = make_pair(k, A[k].smell);
                }
            }
            return ans.first;
        }
    }

    void circle(mapwithant AP[20][20],bool exam = 1)
    {
        int step[20];
        for (int i1 = 0; i1 < 20; i1++)
        {
            step[i1] = 0;
        };
        int  i = findposs(AP[0],step,exam);
        int sum = i ;
        P.push_back(sum);
        suming += AP[0][i].distance;
        while (i != 1)
        {
            sum = i * 20;
            int M = i;
            i = findposs(AP[i],step,exam);
            if (i == -1)
            {
                suming = 0x3f3f3f;
                break;
            }
            suming += AP[M][i].distance;
            sum += i;
            P.push_back(sum);
        };
        cout << "finish" << endl;
    }
    void clear()
    {
        P.clear();
        suming = 0;
    }

};

int main()
{
    vector<string> cities = {
      "Arad", "Bucharest", "Craiova", "Doberta", "Eforie",
      "Fagaras", "Glurgiu", "Hirsova", "Iasi", "Lugoj",
      "Mehadia", "Neamt", "Oradea", "Pitesti", "Rimmicu_Vikea",
      "Sibiu", "Timisoara", "Urziceni", "Vaslui", "Zerind"
    };
    mapwithant AP[20][20];
    for(int i = 0 ;i<20;i++)
    {
        for (int j = 0; j < 20; j++)
        {
            int K;
            cin >> K;
            AP[i][j].distance = K;
            AP[i][j].workwithpointpossible();
        }
    }
    ant a[20];
    for (int k = 0; k < 200; k++)
    {
        for (int i = 0; i < 20; i++)
        {
            a[i].circle(AP);
        };
        for (int i1 = 0; i1 < 20; i1++)
        {
            for (int j1 = 0; j1 < 20; j1++)
            {
                AP[i1][j1].smell = AP[i1][j1].smell *0.88;
            }
        }
        for (int i2 = 0; i2 < 20; i2++)
        {

            for (auto it : a[i2].P)
            {
                AP[it / 20][it % 20].smell += (1000 / a[i2].suming) * AP[it / 20][it % 20].distance;
                AP[it / 20][it % 20].workwithpointpossible();
            }
            a[i2].clear();
        }
    };
    ant ans;
    ans.circle(AP);
    for (auto it : ans.P)
    {
        cout << cities[it % 20] << endl;
    }
    cout << ans.suming << endl;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
